package Top_Interview_Questions.Array;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author: 吕庆龙
 * @Date: 2020/3/12 14:55
 * <p>
 * 功能描述:
 */
public class _0054 {

    public static void main(String[] args) {
        _0054 test = new _0054();
        int[][] matrix = {
                {1, 2, 3, 4},
                {5, 6, 7, 8},
                {9,10,11,12}
        };
        List<Integer> res = test.spiralOrder2(matrix);
        System.out.println(res);
    }
    /**
     * 官方题解,暂时还没看
     */
    public List < Integer > spiralOrder2(int[][] matrix) {
        List ans = new ArrayList();
        if (matrix.length == 0)
            return ans;
        int r1 = 0, r2 = matrix.length - 1;
        int c1 = 0, c2 = matrix[0].length - 1;
        while (r1 <= r2 && c1 <= c2) {
            for (int c = c1; c <= c2; c++) ans.add(matrix[r1][c]);
            for (int r = r1 + 1; r <= r2; r++) ans.add(matrix[r][c2]);
            if (r1 < r2 && c1 < c2) {
                for (int c = c2 - 1; c > c1; c--) ans.add(matrix[r2][c]);
                for (int r = r2; r > r1; r--) ans.add(matrix[r][c1]);
            }
            r1++;
            r2--;
            c1++;
            c2--;
        }
        return ans;
    }




    /**
     * 删除+旋转
     */
    public static List<Integer> spiralOrder1(int[][] matrix) {
        List<Integer> res = new ArrayList<>();
        while (matrix.length > 0) {
            int n = matrix.length;
            int m = matrix[0].length;

            //添加
            for (int i : matrix[0]) {
                res.add(i);
            }

            //删除一行
            if (matrix.length > 1) {
                int[][] matrixtemp = new int[n-1][m];
                for (int i = 1; i < n; i++) {
                    matrixtemp[i - 1] = matrix[i];
                }
                matrix = matrixtemp;

                //旋转（因为删除了一行所以n-1）
                int[][] arr = new int[m][n-1];
                for (int i = 0; i < n-1; i++) {
                    for (int j = 0; j < m; j++) {
                        arr[m - 1 - j][i] = matrix[i][j];
                    }
                }
                matrix=arr;

            } else {
                break;
            }
        }
        return res;
    }


    /**
     * 传说中的直接法
     * https://leetcode-cn.com/problems/spiral-matrix/solution/cxiang-xi-ti-jie-by-youlookdeliciousc-3/
     */
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> ans = new ArrayList<>();
        if(matrix.length == 0) return ans; //若数组为空，直接返回答案
        int u = 0; //赋值上下左右边界
        int d = matrix.length - 1;
        int l = 0;
        int r = matrix[0].length - 1;
        while(true)
        {
            for(int i = l; i <= r; ++i)
                ans.add(matrix[u][i]); //向右移动直到最右
            if(++ u > d) //重新设定上边界，若上边界大于下边界，则遍历遍历完成，下同
                break;
            for(int i = u; i <= d; ++i)
                ans.add(matrix[i][r]); //向下
            if(-- r < l) //重新设定右边界
                break;
            for(int i = r; i >= l; --i)
                ans.add(matrix[d][i]); //向左
            if(-- d < u) //重新设定下边界
                break;
            for(int i = d; i >= u; --i)
                ans.add(matrix[i][l]); //向上
            if(++ l > r) //重新设定左边界
                break;
        }
        return ans;

    }
}
